/**
 * @file
 * @author Nikhil S. Ketkar
 * An optimized data structure for isomorphism type problems. 
 * One way of thinking about this data structure is that it stores all 
 * possible "expansions" from a given vertex. This is exactly the kind of access 
 * required for isomorphism type of problems.
 */
#ifndef EXPANSION_GRAPH_H
#define EXPANSION_GRAPH_H

#include <iostream>
#include <map>
#include <set>

/**
 * An optimized data structure for isomorphism type problems.
 * This data structure is that it stores all possible "expansions" 
 * from a given vertex. This is exactly the kind of access 
 * required for isomorphism type of problems.
 */
template<class V, class E>
class ExpansionGraph
{
 public:
  bool add_vertex(V* v);
  bool add_edge(E *e, V* v1, V* v2);
  bool get_expansions(V *v, std::map<E*, V*> *result);
  void get_vertices(std::set<V* > **result);
  bool check_adjacency(E *e, V *v1, V *v2);
  bool get_expansions_subset(V *v, std::set<E*> *edge_set, std::map<E*, V*> *result);
 private:
  std::set<V *> vertices;
  std::map< V*, std::map<E*, V*> > expansions;
};

/**
 * Add a new vertex, returns false if already present.
 * @param[in] v Vertex to be added.
 * @return @c false if such a vertex is already present, @c true otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::add_vertex(V *v)
{
  // Check if the vertex is already present
  if(expansions.find(v) == expansions.end())
    {
      // Create a new set for expansions and put it as the value for that vertex 
      // index
      std::map<E*, V*> curr_expansions;
      expansions[v] = curr_expansions;
      
      vertices.insert(v);

      return true;
    }
  else
    return false;
}


/**
 * Add a new edge on two previously added vertices.
 * @param[in] e Edge to be added.
 * @param[in] v1 A vertex corresponding to the edge.
 * @param[in] v2 The other vertex.
 * @return @c true if both the vertices are already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::add_edge(E *e, V* v1, V* v2)
{
  // Check if both the vertices have been introduced previously
  if((expansions.find(v1) != expansions.end())  
     && (expansions.find(v2) != expansions.end()))
    {
      // Add expansion for v1 on edge e going to vertex v2
      (expansions[v1])[e] = v2;
      // Add expansion for v2 on edge e going to vertex v1
      (expansions[v2])[e] = v1;
      return true;
    }
    else
      return false;
}

/**
 * Get expansions on a vertex, return false if none exist.
 * @param[in] v Vertex for which expansions are requested.
 * @param[out] result Result location to write to.
 * @return @c true if the vertex is already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::get_expansions(V *v,  std::map<E*, V*> *result)
{
  // Check if vertex is present
  if(expansions.find(v) != expansions.end())
    {
      // Copy the expansions set on to the result
      *result = expansions[v];
      return true;
    }
  else
    return false;
}

/**
 * Get vertices in the graph.
 * @param[out] result The result location to write to.
 */
template<class V, class E>
  void ExpansionGraph<V,E>::get_vertices(std::set<V* > **result) 
{ 
  *result = &vertices;
}


/**
 * Check if two vertices are connected by a given edge. 
 * Note that there are two parts to this check, first is there an edge 
 * between the given vertices and second does this edge have the given 
 * 'value'.
 * @param[in] e The given edge, whose value is relevant, not the graph.
 * @param[in] v1 The first vertex, the particular graph is relevant.
 * @param[in] v2 The other vertex, the particular graph is relevant.
 * @return @c true if check successfull, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V,E>::check_adjacency(E *e, 
                                            V *v1,
                                            V *v2)
{
  // Try to get the constrained expansions for the first vertex
  std::map<E*, V*> expansions1;
  if(get_expansions(v1, &expansions1))
    {
      // Iterate over the expansions
      for(typename std::map<E*, V*>::iterator i = expansions1.begin();
          i != expansions1.end();
          i++)
        if ((*(i->first) == *e) // Check for the correct edge 'value' 
            && ((i->second) == v2)) // Check for the presence of an edge
          return true;
      
      // There is no edge or there is no edge with the given 'value'
      return false;
    }
  // There were no constrained expantions to be found
  else
    return false; 
}

/**
 * Match a vertex to an other vertex in a graph.
 * the other vertex and that the expansions of the first vertex are present on 
 * the other vertex.
 * @param [in] v1 The first vertex to be considered.
 * @param [in] v2 The other vertex to be considered.
 * @param [in] i1 The first graph.
 * @param [in] i2 The other graph.
 * @return @c true if these constraints are satisfied, @c flase otherwise.
 */
template<class V, class E>
  bool match_vertices(V *v1,
                      V *v2, 
                      ExpansionGraph<V, E> *i1,
                      ExpansionGraph<V, E> *i2)
{
  // Check if the vertices themselves match
  if (*v1 == *v2)
    {
      // Get the expansions of the vertices with reference to
      // the graph
      std::map<E*, V*> expansions1, expansions2;
      i1->get_expansions(v1, &expansions1);
      i2->get_expansions(v2, &expansions2);
      
      // Iterate over the expansions of the first vertex. Note here
      // that we are going to erase from the map while we iterate
      // through it so we have to increment the iterator in a way 
      // different from a typical 'for' loop. 
      for(typename std::map<E*, V*>::iterator i = expansions1.begin();
          i != expansions1.end();) 
        {
          // Flag to indicate that match has been found
          bool found = false;

          // Iterate over the expansions of the other vertex. Note here
          // that we are going to erase from the map while we iterate
          // through it so we have to increment the iterator in a way 
          // different from a typical 'for' loop. 
          for(typename std::map<E*, V*>::iterator j = expansions2.begin();
              j != expansions2.end();)
            {
              // Check if the expansion matches
              if((*(i->first) == *(j->first)) && (*(i->second) == *(j->second)))
                {
                  // Erase the expansion in the 'other' vertex expansions 
                  expansions2.erase(j++);

                  // Indicate that the match has been found
                  found = true;

                  // We do not need to iterate any further as a match has been
                  // found
                  break;
                }
              else
                j++; // Iterate over the expansions of the other vertex
            }
          
          // Check if a match for the current expansion was found 
          if (found)
            // Erase the expansion in the 'first' vertex expansions
            expansions1.erase(i++); 
          else
            // The current expansion cound not be matched so the vertices
            // cannot match
            return false;         
          }

      // Check if all the expansions have been matched. 
      // Is this really necessary ?
      if (expansions1.empty())
        return true;
      else
        return false;
    }
  // Vertices themselves do not match, no need to consider expansions
  else
    return false;
}

/**
 * Get matching vertices in two graphs
 * Given two graphs produce and return a many-to-many correspondence
 * between the vertices such that the vertices and their expansions in the first
 * graph are present and identical in the second graph.
 * @param [in] i1 The first graph
 * @param [in] i2 The other graph
 * @param [out] result Result location to write to.
 * @return @c true if all vertices in the first graph have a match in 
 * the other graph, @c false otherwise.
 */
template<class V, class E>
  bool get_vertex_mapping (ExpansionGraph<V, E> *i1, 
                           ExpansionGraph<V, E> *i2,
                           std::multimap<V*, V*> *result )
{
  // Get the vertices of the graphs
  std::set<V*> *vertices1, *vertices2;
  i1->get_vertices(&vertices1);
  i2->get_vertices(&vertices2);
    
  // Iterate over the vertices of the first graph
  for(typename std::set<V*>::iterator i = vertices1->begin();
      i != vertices1->end();
      i++)
    {
      // Flag to indicate that match has been found
      bool found = false;

      // Iterate over the vertices of the second graph
      for(typename std::set<V*>::iterator j = vertices2->begin();
          j != vertices2->end();
          j++)
        {
          // Check if the vertices and their expansions are
          // identical
        if(match_vertices(*i,*j, i1, i2))
          {
            // Indicate that a match has been found
            found = true;
            // Add the correspondence to the result multimap
            result->insert(std::pair<V*, V*>(*i,*j));
          }
        }
      // The current vertex from first graph cound not be matched to
      // any vertex from the other graph so a complete correspondence
      // is not possible
      if(! found)
          return false;
    }
  
  // All vertices have atleast one match
  return true;
}

/**
 * Check if two graphs are isomorphic for a specific vertex mapping. 
 * Given two graphs and a mapping between their vertices check if every 
 * adjacency in the first graph is preserved in the other graph. 
 * @param [in] i1 The first graph.
 * @param [in] i2 The other graph.
 * @param [in] mapping The mapping between vertices to check. 
 * @return @c true if preserved, @c false otherwise.
 */
template<class V, class E>
  bool check_mapping (ExpansionGraph<V, E> *i1, 
                              ExpansionGraph<V, E> *i2, 
                              std::map<V*, V*> *mapping)  
{
  // Iterate over the mapping
  for(typename std::map<V*, V*>::iterator i = mapping->begin();
      i != mapping->end();
      i++)
    {
      // Get the expansions for the current vertex in the first graph
      std::map<E*, V*> *expansions1 = new std::map<E*, V*>;
      
      // Check if it has any expansions
      if(i1->get_expansions(i->first, expansions1))
        {
          // Iterate over the expansions
          for(typename std::map<E*, V*>::iterator j = expansions1->begin();
              j != expansions1->end();
              j++)
            {
              // Check adjacency for the corresponding vertices in the other 
              // graph. Suppose we are given that vertex A is connected to
              // vertex B through edge C in the first graph and we are given
              // a mapping from A to X and from  C to Z. Then we check if there 
              // exists an edge identical in value to C between X and Z.
              if(! i2->check_adjacency
                 (
                  // Edge
                  j->first, 

                  // Corresponding vertex in the other graph, we use the
                  // 'second' of i as the map is from vertices of i1 to the
                  // vertices of i2
                  i->second, 
                  
                  // Corresponding vertex in the other graph, we have the
                  // vertex in i1 and we use the given mapping to find the
                  // corresponding vertex in i2
                  (mapping->find(j->second))->second 
                  ))
                // Even if a single check fails we can return false
                return false;
            }
        }
      // If there are no expansions, trivially true
      else
        return true;
      
      // Delete the expansions fo the current vertex in the first graph
      delete expansions1;
    }
  // All vertices have identical adjacency 
  return true;
}


/**
 * Get expansions on a vertex, constrained by given set of edges.
 * If an edge is not in the set, the expansion through that edge is not present 
 * in the result.
 * @param[in] v Vertex for which expansions are requested.
 * @param[in] edge_set Edge set that constrains the expansions.
 * @param[out] result Result location to write to.
 * @return @c true if the vertex is already present, @c false otherwise.
 */
template<class V, class E>
  bool ExpansionGraph<V, E>::get_expansions_subset
  (
   V *v, 
   std::set<E*> *edge_set, 
   std::map<E*, V*> *result  
   )
{
  // Check if the vertex is present
  if(expansions.find(v) != expansions.end())
    {
      // Copy the expansions set on to the result
      *result = expansions[v];
      
      // Iterate over the expansions
      for(typename std::map<E*, V*>::iterator i = result->begin();
          i != result->end();)
        // Check if the edge on which the current expansion is based
        // is present in the given edge_set
        if(edge_set->find(i->first) == edge_set->end())
          // Erase the expansion if the edge is absent 
          result->erase(i++);
        else
          i++;
      
      return true;
    }
  else
    return false;
}

#endif // EXPANSION_GRAPH_H

